﻿#define _CRT_SECURE_NO_WARNINGS 1

//移除元素

int removeElement(int* nums, int numsSize, int val)
{
    /*方法1
        解题思路：
        1. 从前往后遍历nums，找到val第一次出现的位置
        2. 将val之后的所有元素整体往前搬移，即删除该val
        3. nums中有效元素个数减少一个
        循环进行上述操作，直到nums中所有值为val的元素全部删除完
        时间复杂度 : O(N ^ 2)  空间复杂度 : O(1)*/

    while (1)
    {
        // 1. 在nums中找val出现的位置
        int pos = 0;
        for (; pos < numsSize; ++pos)
        {
            if (nums[pos] == val)
            {
                break;
            }
        }
        // 2. 检测是否找到
        if (pos == numsSize)
            break;
        // 3. 找到值为value的元素--将其删除
        for (int j = pos + 1; j < numsSize; ++j)
        {
            nums[j - 1] = nums[j];
        }
        numsSize--;
    }
    return numsSize;
   /* 方法2优化：
        解题思路 :
    因为题目说了，数组中元素个数最大为100，所以不用动态申请，至二级创建100个元素数组即可
        1. 创建一个100个元素的整形数组temp
        2. 遍历nums，将nums中所有与val不同的元素搬移到temp中
        3. 将temp中所有元素拷贝回nums中
        时间复杂度 : O(N)  空间复杂度 : O(N)*/
        // 1. 申请numSize个元素的新空间
        int temp[100];
        // 2. 将nums中非value的元素搬移到temp中---尾插到temp中
        int count = 0;
        for (int i = 0; i < numsSize; ++i)
        {
            if (nums[i] != val)
            {
                temp[count] = nums[i];
                ++count;
            }
        }
        // 3. 将temp中删除val之后的所有元素拷贝到nums中
        memcpy(nums, temp, sizeof(int) * count);
        return count;

    //双指针
    int src = 0;
    int dst = 0;
    while (src < numsSize)
    {
        if (nums[src] != val)
        {
            nums[dst++] = nums[src++];
        }
        else
        {
            src++;
        }
    }

    return dst;
}
/*
    解题思路:
        1. 设置一个变量count，用来记录nums中值等于val的元素的个数
        2. 遍历nums数组，对于每个元素进行如下操作：
            a. 如果num[i]等于val，说明值为val的元素出现了一次，count++
            b. 如果nums[i]不等于元素，将nums[i]往前搬移count个位置
                因为nums[i]元素之前出现过count个值等于val的元素，已经被删除了
                因此次数需要将nums[i]往前搬移
        3. 返回删除之后新数组中有效元素个数

    时间复杂度：O(N)   空间复杂度：O(1)
 */
int removeElement(int* nums, int numsSize, int val) {
    int count = 0;
    for (int i = 0; i < numsSize; ++i)
    {
        if (nums[i] == val)
        {
            count++;
        }
        else
        {
            nums[i - count] = nums[i];
        }
    }


    return numsSize - count;
}




//合并两个有序数组

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    //int src1 = 0;
    //int src2 = 0;
    //int dst[m + n];
   /* int cul;
    while (src1 < m || src2 < n)
    {
        if (src1 == m)
        {
            cul = nums2[src2++];
        }
        else if (src2 == n)
        {
            cul = nums1[src1++];
        }
        else if (nums1[src1] < nums2[src2])
        {
            cul = nums1[src1++];
        }
        else {
            cul = nums2[src2++];
        }
        dst[src1 + src2 - 1] = cul;
    }
    for (int i = 0;i < m + n;i++)
    {
        nums1[i] = dst[i];
    }*/
}

/*
    解题思路:
      1. 从后往前遍历数组，将nums1和nums2中的元素逐个比较
         将较大的元素往nums1末尾进行搬移
      2. 第一步结束后，nums2中可能会有数据没有搬移完，将nums2中剩余的元素逐个搬移到nums1

   ﻿时间复杂度：O(m+n)
   空间复杂度: O(1)
*/﻿
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
//    // end1、end2：分别标记nums1 和 nums2最后一个有效元素位置
//    // end标记nums1的末尾，因为nums1和nums2中的元素从后往前往nums1中存放
//    // ，否则会存在数据覆盖
//    int end1 = m - 1;
//    int end2 = n - 1;
//    int index = m + n - 1;
//
//
//    // 从后往前遍历，将num1或者nums2中较大的元素往num1中end位置搬移
//    // 直到将num1或者num2中有效元素全部搬移完
//    while (end1 >= 0 && end2 >= 0)
//    {
//        if (nums1[end1] > nums2[end2])
//        {
//            nums1[index--] = nums1[end1--];
//        }
//        else
//        {
//            nums1[index--] = nums2[end2--];
//        }
//    }
//
//
//    // num2中的元素可能没有搬移完，将剩余的元素继续往nums1中搬移
//    while (end2 >= 0)
//    {
//        nums1[index--] = nums2[end2--];
//    }
//
//
//    // num1中剩余元素没有搬移完 ---不用管了，因为num1中剩余的元素本来就在num1中
//}


